前言

天啊今天整個非常趕，23:00到家打開發現今天是hard的題目(446. Arithmetic Slices II - Subsequence)，匆忙看了一下，感覺來不急消化後寫出來，先來拿個以前做過的經典題目應急~
我們來看看這題吧！322. Coin Change，是屬於top 100 liked的一題，也是DP的經典題目啊！

想法

這題目乍看之下你會有什麼想法呢？如果是台灣的情況，有1塊錢,5塊錢,10塊錢,50塊錢，你應該覺得這有夠直覺不用算，最少的情形一定是先/50+餘數/10+餘數/5+餘數/1，就好啦！有夠直覺，而且必定正確！
但這題可不能這樣算！為什麼呢？如果今天的錢幣面額是2,7,10，我隨便亂舉，那如果現在要湊18塊錢，你照上面的想法直接算18/10，先用10塊，剩下8塊/7，再用一個7塊，挖，尷尬了，現在剩1塊，但我面額最小只有2塊，湊不出來！
但答案並不是湊不出來，因為我明明就可以用1個10塊跟4個2塊解決啊！
p.s.你也可以想想看為什麼台灣的1,5,10情形一定可以直接用上述那種簡單暴力的做法算出來XD
為什麼說它是經典的題目呢？試想昨天提到的DP概念，我們是不是可以往回推前一個狀態呢？現在我們需要18塊，我們可以知道它可以湊到16塊再加一個2元硬幣，或是湊到13塊再加一個5元硬幣，或是湊到8塊再加一個10元硬幣，然後要求最少的硬幣的情況下，我們是不是就找到湊到16塊/13塊/8塊的情形中，最少的那種，再+1就會是湊到18塊的答案了呢？這樣是不是有想法了呢？
那我們就又可以出動我們的紀錄陣列/矩陣啦！我們現在要湊到amount元，現在面額有coins面額的情形，我們可以建立一個amount+1那麼大的陣列來記錄：(為什麼要+1?因為我們需要0元的數量比較好算一點。繼續看就知道了)
第二個amount+1是我們給這個陣列的初始值，給的原因是要確保一個肯定比正確答案來得大的數值(題目說面額最小的可能是1元，所以絕對不會出現100塊要101個硬幣才能湊出來的情形~)

vector<int> dp(amount+1,amount+1);

接下來怎麼做呢？我們就開始從前面往後推吧！針對現在的每一個暫時的amount，我們要去求它最少的硬幣數量多少，那就是去算該amount-各硬幣面額的情況下的數量，然後再+1；那如果amount-下去已經低於該面額就不用算了(就是 現在我只差3塊錢，但目前這個面額是5，那就不用考慮啦QQ)，那以下就是照這個邏輯的完整程式了：

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        // set a value that is guaranteed to bigger than the possible answer
        // the smallest possible coin value is 1, so there may not be anwer that has to have amount+1 coins to build up the amount
        int ub = amount + 1;
        // record the smallest coins to get the each amount
        vector<int> dp(amount + 1, ub);
        // sort the coins so we could consider less cases
        sort(coins.begin(), coins.end());
        // start from 0 coins
        dp[0] = 0;
        // compute each amount coin numbers from 0
        for (int i = 1; i <= amount; ++i) {
            // consider the last coin as each coins value
            for (int j = 0; j < coins.size(); ++j) {
                // ensure dp[i - coins[j]] is valid
                if (i-coins[j]<0) {
                    continue;
                }
                dp[i] = min(dp[i], dp[i - coins[j]] + 1);
            }
        }
        
        return dp[amount]!=ub?dp[amount]:-1;
    }
};

結語

leetcode的每日挑戰截止時間其實是台灣下午3點，以後還是前一天先寫好題目隔天拿前一天的題目發文好了Orz